package easy

/*F1
时间复杂度:O(N)
空间复杂度:O(1) 除了最终返回的切片以外，不需要额外的辅助空间

dp[i] = dp[i>>1] + i & 1
*/

func countBits(n int) []int {
	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		dp[i] = dp[i>>1] + i&1
	}
	return dp
}

/*F2
时间复杂度:O(N)
空间复杂度:O(1) 除了最终返回的切片以外，不需要额外的辅助空间

布莱恩-肯尼根算法 i&(i-1) 会将i最右边的1变成0，例如 10100 -> 10100 & 10011 => 10000
dp[i] = dp[i&(i-1)] + i & 1

*/

func countBits1(n int) []int {
	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		dp[i] = dp[i&(i-1)] + 1
	}
	return dp
}

/*F3
时间复杂度:O(N)
空间复杂度:O(1) 除了最终返回的切片以外，不需要额外的辅助空间

布莱恩-肯尼根算法 i&(i-1) == 0时，记录当前最高位为highestBit, 后面的循环当i增大时，增大的只是小于最高为的位置上的数，递推公式
dp[i] = dp[i-highestBit] + i

*/

func countBits2(n int) []int {
	dp := make([]int, n+1)
	var highestBit int
	for i := 1; i <= n; i++ {
		if i&(i-1) == 0 {
			highestBit = i
		}
		dp[i] = dp[i-highestBit] + 1
	}
	return dp
}

/*F4
时间复杂度:O(NlogN) N个数,每个数需要logN
空间复杂度:O(1)

*/
// CountBits 通过布莱恩-肯尼跟算法得到每个数中的二进制表示中1的个数
func CountBits4(num int) []int {
	ans := []int{0}
	for i := 1; i <= num; i++ {
		count := 0
		t := i
		for t > 0 {
			count++
			t = (t - 1) & t
		}
		ans = append(ans, count)
	}
	return ans
}